{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MFE 230P: ASSIGNMENT IV\n",
    "**YOUR STUDENT ID** \\\\ YOUR NAME \\\\ YOUR GROUP NAME"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. A Simple Exercise in Diversification\n",
    "\n",
    "You have \\$12,000 to invest at the beginning of the year, and three different funds from which to choose. The municipal bond fund has a 7% yearly return, the local bank's Certificates of Deposit (CDs) has an 8% return, and a high-risk account has an expected (hoped-for) 12% return. To minimize risk, you decide not to invest any more than \\$2,000 in the high-risk account. For tax reasons, you need to invest at least three times as much in the municipal bonds as in the bank CDs.\n",
    "\n",
    "Denote by $x,y,z$ the amounts (in thousands) invested in bonds, CDs, and high-risk account, respectively. Assuming the year-end yields are as expected, what are the optimal investment amounts for each fund? Your answer should include a problem formulation (as a mathematical program), source code used to solve this problem using only `cvxpy`, and the optimal investment amounts for each account."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SOLUTION.\n",
    "\n",
    "_Your solution here._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Modeling Transaction Costs with _Berhu_\n",
    "\n",
    "In this question, we'll turn to the reversed Huber function which can be used to robustly model transaction costs and market impact. Specifically, we consider the following portfolio optimization problem\n",
    "\n",
    "\\begin{align}\n",
    "    & \\underset{x \\in \\mathbb{R}^p}{\\text{maximize}} & & \\hat{r}^\\top x - \\lambda x^\\top Cx - c \\cdot T(x-x^0)  \\\\\n",
    "    & \\text{subject to} & &  \\sum_{i=1}^p x_i = 1, \\ x \\ge 0\n",
    "\\end{align}\n",
    "\n",
    "where $C$ is the empirical covariance matrix, $\\hat{r}$ is the empirical mean based on historical data, and $\\lambda$ as well as $c$ are hyper-parameters to be discussed. The function $T(\\cdot)$ represents transaction costs and market impact, $x^0 \\in \\mathbb{R}^p$ is the vector of initial positions. The function $T$ takes the form\n",
    "\n",
    "$$T\\left(x - x^0\\right)  = \\sum_{i=1}^p B_M\\left(x_i - x_i^0\\right)$$\n",
    "\n",
    "where the function $B_M(\\cdot)$ is piece-wise linear for small $x$ and quadratic for large $x$. In this way, we seek to capture the fact that transaction costs are dominant for smaller trades while market impact kicks in for larger ones. Precisely, we define $B_M$ to be the so-called _berhu_ or _reversed Huber_ function with\n",
    "cut-off parameter $M \\geq 0$. That is, for a scalar $z$, \n",
    "\n",
    "$$B_M(z) := \\left\\{ \n",
    "    \\begin{array}{ll}\n",
    "\t|z| & \\mbox{if } |z| \\le M, \\\\\n",
    "\t\\frac{z^2+M^2}{2M} & \\mbox{otherwise.}\n",
    "    \\end{array}\n",
    "\\right.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A. Inner Problem Characterization\n",
    "\n",
    "Prove that the reversed Huber function is equivalent to the following optimization problem\n",
    "\n",
    "$$B_M(z) = \\min_{v,w} \\: v+w+\\frac{w^2}{2M} \\text{ subject to } |z| \\le v+w, \\;\\; v \\le M, \\;\\; w \\ge 0$$\n",
    "\n",
    "Is the reversed Huber function convex in $z$? Justify your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SOLUTION.\n",
    "\n",
    "_Your solution here._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### B. Outer Problem Characterization\n",
    "\n",
    "Show that, for given $x, x^0 \\in \\mathbb{R}^p$\n",
    "\n",
    "$$T\\left(x-x^0\\right) = \\min_{w,v} \\: \\mathbf{1}^\\top (v+w)+\\frac{w^\\top w}{2M} \\text{ subject to } v \\le M \\mathbf{1}, \\;\\; w \\ge 0, \\;\\; \\left|x-x^0\\right| \\le v+w$$\n",
    "\n",
    "where, $v,w \\in \\mathbb{R}^p$, $\\mathbf{1} \\in \\{1\\}^p$ is the vector of ones, and the absolute value function $|\\cdot|$ is applied component-wise on vectors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SOLUTION.\n",
    "\n",
    "_Your solution here._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### C. A Tractable Convex Formulation\n",
    "\n",
    "Now re-formulate the optimization problem provided in the preamble as a convex optimization problem. Which programming class does this problem belong to (LP, QP, SOCP, etc)?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SOLUTION.\n",
    "\n",
    "_Your solution here._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Robust Portfolio Optimization\n",
    "\n",
    "In this question, we consider a robust portfolio optimization problem, which can be formulated in the SOCP form. Markowitz portfolio theory states that an investor can reduce portfolio risk by\n",
    "holding a diversified portfolio of assets. A portfolio is ``efficient'' if it achieves the highest expected return with a given risk (measured by standard deviation). The set of efficient portfolios form a curve on the return versus standard deviation plane. The curve is called efficient frontier. To compute and plot the efficient frontier, we can formulate the portfolio optimization problem as the following quadratic programming (QP) problem:\n",
    "\n",
    "\\begin{align}\n",
    "    & \\underset{x \\in \\mathbb{R}^p}{\\text{minimize }} & & x^\\top Cx \\\\\n",
    "    & \\text{ subject to } & & \\hat{r}^\\top x \\ge t, \\sum_{i=1}^p x_i = 1\n",
    "\\end{align}\n",
    "\n",
    "Here, $x \\in \\mathbb{R}^p$ is the asset allocation vector and $p$ is the number of assets. Each component $x_i$ corresponds to the percentage of money invested in the $i^{th}$ asset. Consequently, we have the constraint that the sum of $x_i$ is $1$. The return vector $r \\in \\mathbb{R}^p$ is a random variable with $\\hat{r}$ denoting its expectation and $C$ its corresponding covariance matrix. In practice, we usually use empirical mean and covariance matrix of historical asset return data to estimate $\\hat{r}$ and $C$. The parameter $t \\geq 0$ is the target expected return of the portfolio."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A. Markowitz's Efficient Frontier\n",
    "\n",
    "Excuting the next cell will create a `numpy` array, `data`, containing the log-return time series for $p=77$ stocks over $n=503$ days, from January 2007 to December 2008. Compute the sample mean vector $\\hat{r}$ and covariance matrix $C$. Solve the Markowitz portfolio problem by sweeping the target return $t$ from $0$ to $10t^*$, where\n",
    "\n",
    "$$t^* := \\text{max}\\{\\hat{r}_1, \\cdots, \\hat{r}_p\\}$$\n",
    "\n",
    "Plot the efficient frontier on a 2D plane where the $x$-axis corresponds to the standard deviation of the portfolio and the $y$-axis to the expected return."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "data = np.loadtxt(\n",
    "    '../../data/77_stocks.csv',\n",
    "    delimiter=','\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SOLUTION.\n",
    "\n",
    "_Your solution here._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### B. Robust Mean-Variance Optimization\n",
    "\n",
    "We now consider a robust version of portfolio optimization problem given by\n",
    "\n",
    "\\begin{align}\n",
    "    & \\underset{x \\in \\mathbb{R}^p}{\\text{minimize }} & & x^\\top C x \\\\\n",
    "    & \\text{ subject to } & & x^\\top r \\geq t, \\ \\forall r \\in \\mathcal{U} , \\ \\sum_{i = 1}^p x_i = 1\n",
    "\\end{align}\n",
    "\n",
    "where $\\mathcal{U}=\\left\\{\\hat{r}+\\alpha C^{1/2}v \\mid \\|v\\|_2 \\leq 1\\right\\}$ is an $\\alpha$-standard deviation uncertainty set for $r$ ($\\alpha \\ge 0$ being a scalar). Show that the aforementioned program can be reformlated as the following SOCP:\n",
    "\n",
    "\\begin{align} \n",
    "    & \\underset{x \\in \\mathbb{R}^p}{\\text{minimize }} & & x^\\top C x \\\\\n",
    "    & \\text{ subject to } & & \\alpha \\left\\|C^{1/2} x \\right\\|_2 \\leq x^\\top \\hat r - t, \\ \\sum_{i = 1}^p x_i = 1\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SOLUTION.\n",
    "\n",
    "_Your solution here._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### C. Defining the Confidence Set\n",
    "\n",
    "Now let's find an interpretation for the parameter $\\alpha$. Assuming that the return vector $r$ is a Gaussian random variable with mean $\\hat{r}$ and positive-definite covariance $C$, we have \n",
    "\n",
    "$$P(r_1, \\dots, r_p) = (2\\pi)^{-\\frac{p}{2}} \\cdot \\mathbf{det}(C)^{-\\frac{1}{2}} \\cdot \\exp\\left(-\\frac{1}{2}(r-\\hat{r})^\\top C^{-1} (r - \\hat{r})\\right)$$\n",
    "\n",
    "We seek to construct our portfolio such that the probability of the return being less than a target value $t$ is less than $\\epsilon$, or, stated mathematically,\n",
    "\n",
    "\\begin{align}\n",
    "    & \\underset{x \\in \\mathbb{R}^p}{\\text{minimize }} & & x^\\top C x \\\\\n",
    "    & \\text{ subject to } & & \\text{Pr}\\left(r^\\top x \\le t\\right) \\le \\epsilon, \\ \\sum_{i = 1}^p x_i = 1\n",
    "\\end{align}\n",
    "\n",
    "Show that the constraint\n",
    "\n",
    "$$\\text{Pr}\\left(r^\\top x \\le t\\right) \\le \\epsilon$$\n",
    "\n",
    "is equivalent to\n",
    "\n",
    "$$\\kappa(\\epsilon) \\left\\|C^{1/2} x \\right\\|_2 \\leq x^\\top \\hat r - t$$\n",
    "\n",
    "where $\\kappa(\\epsilon) = \\Phi^{-1}(1-\\epsilon)$ and $\\Phi^{-1}(\\cdot)$ is the quantile function of the standard normal distribution. _**Hint:** for a Gaussian random vector $y \\sim \\mathcal{N}(0, \\mathbb{I})$, we have that $\\text{Pr}(a^\\top y \\le t) = \\Phi\\left(t/\\|a\\|_2\\right)$._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SOLUTION.\n",
    "\n",
    "_Your solution here._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### D. The Robust Efficient Frontier\n",
    "\n",
    "Sweep the parameter $t$ from $0$ to $10t^*$, solve the above portfolio optimization problem for each $t$ and plot the efficient frontier. Setting $\\alpha = 0$ will recover Markowitz's efficient frontier. Set $\\alpha = 0.2$ to obtain a robust efficient frontier. Construct the efficient frontiers based on the empirical mean and covariance from historical data (these may not be the same as the mean and covariance that the market eventually realizes). Compare the two efficient frontiers and briefly comment."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SOLUTION.\n",
    "\n",
    "_Your solution here._"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
